//
// Created by gushen610140 on 2024/4/28.
//

#ifndef DATASTRUCTURECOURSE_GGRAPH_H
#define DATASTRUCTURECOURSE_GGRAPH_H


#include <iostream>
#include <queue>
#include <set>
#include "GDisjointSet.h"

class [[maybe_unused]] GGraph {
private:
    int _vertexNum;
    int _edgeNum;
    int **_adjMatrix;
    int *_weightList;

    void _dfs(bool *visited, int v) {
        visited[v] = true;
        std::cout << v << " ";
        for (int i = 0; i < _vertexNum; i++) {
            if (!visited[i] && _adjMatrix[v][i] == 1) {
                _dfs(visited, i);
            }
        }
    }

    void _bfs(bool *visited, std::queue<int> &q) {
        while (!q.empty()) {
            int v = q.front();
            std::cout << v << " ";
            q.pop();
            for (int i = 0; i < _vertexNum; i++) {
                if (!visited[i] && _adjMatrix[v][i] == 1) {
                    q.push(i);
                    visited[i] = true;
                }
            }
        }
    }

    void _tarjan(int curNode, int &time, int *dfsSequence, int *backTrack, int *parent, std::set<int> &cutPoint) {
        // 标记 dfs 时间戳
        dfsSequence[curNode] = time;
        // 初始为回溯自己
        backTrack[curNode] = time;
        time++;
        // 记录孩子数量，用于判断 _root 情况
        int child = 0;
        for (int i = 0; i < _vertexNum; ++i) {
            // 如果边存在
            if (_adjMatrix[curNode][i] != 0) {
                // 如果连通的结点没有被访问过
                if (dfsSequence[i] == 0) {
                    child++;
                    parent[i] = curNode;
                    // 继续 dfs 进行标记
                    _tarjan(i, time, dfsSequence, backTrack, parent, cutPoint);
                    // 下方所有 dfs 完成 开始判断当前结点是否是割点
                    // 当前结点是 _root 结点 且有两个以上儿子 一定是割点
                    if (parent[curNode] == -1 && child >= 2) {
                        cutPoint.insert(curNode);
                    }
                    // 当前结点的孩子不可以通过回溯边绕过当前结点
                    if (parent[curNode] != -1 && backTrack[i] >= dfsSequence[curNode]) {
                        cutPoint.insert(curNode);
                    }
                    // 如果当前结点可以通过孩子的边回到更早的路径 更新回溯
                    backTrack[curNode] = std::min(backTrack[curNode], backTrack[i]);
                } else if (parent[curNode] != i) { // 如果连通结点被访问了 但可能是一个祖先
                    backTrack[curNode] = std::min(backTrack[curNode], backTrack[i]);
                }
            }
        }

    }

public:
    GGraph() {
        _vertexNum = 0;
        _edgeNum = 0;
        _adjMatrix = nullptr;
        _weightList = nullptr;
    }

    int **adjMatrix() {
        return _adjMatrix;
    }

    int vertexNum() {
        return _vertexNum;
    }

    int edgeNum() {
        return _edgeNum;
    }

    void showMatrix() {
        for (int i = 0; i < _vertexNum; ++i) {
            for (int j = 0; j < _vertexNum; ++j) {
                std::cout << _adjMatrix[i][j] << ' ';
            }
            std::cout << std::endl;
        }
    }

    // 矩阵形式创建
    void createGraph(int vertexNum) {
        _vertexNum = vertexNum;
        // 初始化 adjMatrix 初始距离为无穷 即不连通
        _adjMatrix = new int *[_vertexNum];
        for (int i = 0; i < _vertexNum; i++) {
            _adjMatrix[i] = new int[_vertexNum];
        }
        // 根据矩阵填充 adjMatrix
        for (int i = 0; i < vertexNum; ++i) {
            for (int j = 0; j < vertexNum; ++j) {
                int value;
                std::cin >> value;
                _adjMatrix[i][j] = value;
            }
        }
    }

    // 边形式创建
    void createGraph(int vertexNum, int edgeNum) {
        _vertexNum = vertexNum;
        _edgeNum = edgeNum;
        _adjMatrix = new int *[_vertexNum];
        for (int i = 0; i < _vertexNum; i++) {
            _adjMatrix[i] = new int[_vertexNum];
        }
        for (int i = 0; i < _vertexNum; ++i) {
            for (int j = 0; j < _vertexNum; ++j) {
                // 用 0 标记不连通
                _adjMatrix[i][j] = 0;
            }
        }
        // 优先记录权重
        _weightList = new int[_vertexNum];
        for (int i = 0; i < _vertexNum; ++i) {
            std::cin >> _weightList[i];
        }
        for (int i = 0; i < _edgeNum; ++i) {
            int origin, destination;
            std::cin >> origin >> destination;
            // 数据修复
            origin--;
            destination--;
            // 有向图
            _adjMatrix[origin][destination] = 1;
        }
    }

    void dfs() {
        bool *visited = new bool[_vertexNum];
        for (int i = 0; i < _vertexNum; i++) {
            visited[i] = false;
        }
        for (int i = 0; i < _vertexNum; i++) {
            if (!visited[i]) {
                _dfs(visited, i);
            }
        }
        delete[] visited;
    }

    void bfs() {
        bool *visited = new bool[_vertexNum];
        std::queue<int> q;
        for (int i = 0; i < _vertexNum; i++) {
            visited[i] = false;
        }
        for (int i = 0; i < _vertexNum; i++) {
            if (!visited[i]) {
                q.push(i);
                visited[i] = true;
                _bfs(visited, q);
            }
        }
        delete[] visited;
    }

    int prim() {
        // 计算最小生成树的权重
        int sum = 0;
        // 在 dist 数组中记录了每个结点到生成树的最短距离
        int *dist = new int[_vertexNum];
        for (int i = 0; i < _vertexNum; i++) {
            dist[i] = INT_MAX;
        }
        // 将第一个定点放入生成树
        dist[0] = 0;
        // 更新 dist 数组，即初始结点的边即为其他结点到生成树的距离
        for (int e = 0; e < _vertexNum; e++) {
            if (_adjMatrix[0][e] != 0) {
                dist[e] = _adjMatrix[0][e];
            }
        }
        // 生成最小生成树还需要遍历 n-1 次
        for (int count = 0; count < _vertexNum - 1; count++) {
            // 找到需要添加边的结点
            int minDist = INT_MAX, minIndex = -1;
            for (int v = 0; v < _vertexNum; v++) {
                // 要找的结点不能已经存在于生成树中
                if (dist[v] != 0 && dist[v] < minDist) {
                    minDist = dist[v];
                    minIndex = v;
                }
            }
            // 处理生成树新加入的边
            sum += minDist;
            // 将找到的结点添加到生成树中
            dist[minIndex] = 0;
            // 更新 dist 数组，结点的边存在且该边连接的结点不再生成树且改边的距离小于原来记录的最短距离
            for (int e = 0; e < _vertexNum; e++) {
                if (_adjMatrix[minIndex][e] != -1 && dist[e] != 0 && _adjMatrix[minIndex][e] < dist[e]) {
                    dist[e] = _adjMatrix[minIndex][e];
                }
            }
        }
        delete[] dist;
        return sum;
    }

    int kruskal() {
        // 计算最小生成树的权重
        int sum = 0;
        // 定义边配合 kruskal 算法使用
        class GEdge {
        public:
            int value;
            int start;
            int end;
        };
        // 开出边数组方便 kruskal 算法使用
        GEdge *edges = new GEdge[_edgeNum];
        int edgeIndex = 0;
        // 放入边
        for (int i = 0; i < _vertexNum; i++) {
            for (int j = 0; j < _vertexNum; j++) {
                if (_adjMatrix[i][j] != 0) {
                    edges[edgeIndex++] = GEdge{_adjMatrix[i][j], i, j};
                }
            }
        }
        // 利用冒泡排序对边排序
        for (int i = 0; i < _edgeNum - 1; i++)
            for (int j = 0; j < _edgeNum - 1 - i; j++)
                if (edges[j].value > edges[j + 1].value)
                    std::swap(edges[j], edges[j + 1]);

        // 利用并查集判断边的循环
        GDisjointSet ds(_vertexNum);

        // 记录已经生成树的边数量
        int edgeCount = 0;
        // 遍历这些边来生成最小生成树
        for (int i = 0; i < _edgeNum; i++) {
            if (edgeCount == _vertexNum) {
                break;
            }
            int rootStart = ds.find(edges[i].start);
            int rootEnd = ds.find(edges[i].end);
            // 若两个结点不在同一集合中，代表这条边可以加入生成树
            if (rootStart != rootEnd) {
                // 合并两个集合
                ds.unite(rootStart, rootEnd);
                sum += edges[i].value;
                edgeCount++;
            }
        }

        delete[] edges;
        return sum;
    }

    int *dijkstra(int origin) {
        // dist 数组记录从源到其他结点的最短距离
        int *dist = new int[_vertexNum];
        // visited 数组记录已经完成最短路径求值的结点
        bool *visited = new bool[_vertexNum];
        for (int i = 0; i < _vertexNum; ++i) {
            dist[i] = INT_MAX;
            visited[i] = false;
        }
        // 放入源
        dist[origin] = 0;
        // 完成最短路径还需要处理 n 次
        for (int count = 0; count < _vertexNum; ++count) {
            // 找到目前没有确定最短路径结点中的最短路径结点
            int minDist = INT_MAX, minIndex = -1;
            for (int v = 0; v < _vertexNum; ++v) {
                if (!visited[v] && dist[v] < minDist) {
                    minDist = dist[v];
                    minIndex = v;
                }
            }
            // dist 数组中已经全部标记或无法到达
            if (minIndex == -1) {
                break;
            }
            // 标记为已经完成最短路径生成
            visited[minIndex] = true;
            // 更新源到各个顶点的最短距离
            for (int i = 0; i < _vertexNum; ++i) {
                // 必须判断边是不存在的情况 否则 int 会溢出
                if (!visited[i] && dist[i] > dist[minIndex] + _adjMatrix[minIndex][i]) {
                    dist[i] = _adjMatrix[minIndex][i] + dist[minIndex];
                }
            }
        }
        delete[] visited;
        return dist;
    }

    int **floyd() {
        // dist 二维矩阵存放顶点到顶点的距离
        int **dist = new int *[_vertexNum];
        for (int i = 0; i < _vertexNum; ++i) {
            dist[i] = new int[_vertexNum];
        }
        // 填充初始距离
        for (int i = 0; i < _vertexNum; ++i) {
            for (int j = 0; j < _vertexNum; ++j) {
                dist[i][j] = _adjMatrix[i][j];
            }
        }
        // 询问绕过 k 结点是否能使 i, j 之间距离缩短
        for (int k = 0; k < _vertexNum; ++k) {
            for (int i = 0; i < _vertexNum; ++i) {
                for (int j = 0; j < _vertexNum; ++j) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
        return dist;
    }

    std::set<int> tarjan() {
        int time = 1;
        // 存储割点
        std::set<int> cutPoint;
        // 记录 dfs 时间戳
        int *dfsSequence = new int[_vertexNum]();
        // 记录能够回溯到的最早的结点
        int *backTrack = new int[_vertexNum]();
        // 记录当前结点的父亲
        int *parent = new int[_vertexNum];
        // parent 数组可能父亲是 0 所以不能赋初始值为 0
        for (int i = 0; i < _vertexNum; ++i) {
            parent[i] = -1;
        }

        for (int i = 0; i < _vertexNum; ++i) {
            if (dfsSequence[i] == 0) {
                _tarjan(i, time, dfsSequence, backTrack, parent, cutPoint);
            }
        }

        delete[] parent;
        delete[] backTrack;
        delete[] dfsSequence;

        return cutPoint;
    }

    int *topologicalSort() {
        // 存储拓补排序的结果
        int *topologicalSortList = new int[_vertexNum];
        // 记录拓补排序的删除结点数量 用于检测是否存在环
        int deletedNodeCount = 0;
        // 存储每个结点的入度
        int *inDegree = new int[_vertexNum];
        // 初始化入度
        for (int i = 0; i < _vertexNum; ++i) {
            int inDegreeCount = 0;
            for (int j = 0; j < _vertexNum; ++j) {
                if (_adjMatrix[j][i] != 0) {
                    inDegreeCount++;
                }
            }
            inDegree[i] = inDegreeCount;
        }
        // 用优先队列存储找到的入度为 0 的结点 小顶堆方便排序的唯一性
        std::priority_queue<int, std::vector<int>, std::greater<int>> deletedNodeQueue;
        // 寻找初始的入度为 0 的结点
        for (int i = 0; i < _vertexNum; ++i) {
            if (inDegree[i] == 0) {
                deletedNodeQueue.push(i);
            }
        }
        // 记录当前结点是否被删除
        bool *isDeleted = new bool[_vertexNum];
        for (int i = 0; i < _vertexNum; ++i) {
            isDeleted[i] = false;
        }
        // 逐步删除入度为 0 的结点
        while (!deletedNodeQueue.empty()) {
            // 获取准备删除的结点
            int deletedNode = deletedNodeQueue.top();
            deletedNodeQueue.pop();
            // 标记删除结点
            isDeleted[deletedNode] = true;
            // 记录拓补排序路径
            topologicalSortList[deletedNodeCount] = deletedNode;
            // 记录删除数量
            deletedNodeCount++;
            // 更新以当前被删除结点出发的被连接到结点的入度数组
            for (int i = 0; i < _vertexNum; ++i) {
                if (_adjMatrix[deletedNode][i] != 0 && !isDeleted[i]) {
                    inDegree[i]--;
                    // 判断若被连接结点的入度为 0 则入栈
                    if (inDegree[i] == 0) {
                        deletedNodeQueue.push(i);
                    }
                }
            }
        }
        // 判断是否有环
        if (deletedNodeCount != _vertexNum) {
            throw std::runtime_error("unworkable project");
        }
        delete[] isDeleted;
        delete[] inDegree;
        return topologicalSortList;
    }

    void criticalPath() {
        // 拓补排序结果 利用异常抛出检测是否有环
        int *topologicalList;
        try {
            topologicalList = topologicalSort();
        } catch (const std::runtime_error e) {
            std::cout << e.what();
            return;
        }
        // 工程的最早开始时间
        int *earliestStart = new int[_vertexNum]();
        // 计算工程的最早开始时间
        for (int i = 0; i < _vertexNum; ++i) {
            int curEvent = topologicalList[i];
            for (int nextEvent = 0; nextEvent < _vertexNum; ++nextEvent) {
                // 如果边存在 更新最早开始时间
                if (_adjMatrix[curEvent][nextEvent] != 0) {
                    int eventDuration = _adjMatrix[curEvent][nextEvent];
                    earliestStart[nextEvent] = std::max(earliestStart[nextEvent],
                                                        earliestStart[curEvent] + eventDuration);
                }
            }
        }
        // 输出最早开始时间 也是工程的总时间 也是 earliest 数组中的最大
        int projectTime = 0;
        for (int i = 0; i < _vertexNum; ++i) {
            projectTime = std::max(projectTime, earliestStart[i]);
        }
        std::cout << projectTime << std::endl;
        // 工程的最晚开始时间
        int *latestStart = new int[_vertexNum];
        for (int i = 0; i < _vertexNum; ++i) {
            latestStart[i] = projectTime;
        }
        // 计算工程的最晚开始时间
        for (int i = _vertexNum - 1; i >= 0; --i) {
            int curEvent = topologicalList[i];
            for (int prevEvent = 0; prevEvent < _vertexNum; ++prevEvent) {
                if (_adjMatrix[prevEvent][curEvent] != 0) {
                    int eventDuration = _adjMatrix[prevEvent][curEvent];
                    latestStart[prevEvent] = std::min(latestStart[prevEvent],
                                                      latestStart[curEvent] - eventDuration);
                }
            }
        }
        // 计算活动的最早开始时间和最晚开始时间
        int *earliest = new int[_edgeNum];
        int *latest = new int[_edgeNum];
        int edgeIndex = 0;
        for (int i = 0; i < _vertexNum; ++i) {
            for (int j = 0; j < _vertexNum; ++j) {
                if (_adjMatrix[i][j] != 0) {
                    earliest[edgeIndex] = earliestStart[i];
                    latest[edgeIndex] = latestStart[j] - _adjMatrix[i][j];
                    // 输出关键路径
                    if (earliest[edgeIndex] == latest[edgeIndex]) {
                        std::cout << i + 1 << "->" << j + 1 << std::endl;
                    }
                    edgeIndex++;
                }
            }
        }
        delete[] earliestStart;
        delete[] latestStart;
        delete[] earliest;
        delete[] latest;
        delete[] topologicalList;
    }
};


#endif //DATASTRUCTURECOURSE_GGRAPH_H
